⟸ pàgina anterior ⟸

Exercici 6 (Tasca 1).

(homomorphism, theory of languages)

Homomorfismes I – propietats bàsiques

Sigui \sigma :\Sigma^* \to \Sigma^* una funció. Quines de les definicions següents de \sigma defineix un homomorfisme? És a dir, quines satisfan que per mots x,y\in \Sigma^* qualssevol, \sigma(xy)=\sigma(x)\sigma(y)? Sigui w=a_1a_2\cdots a_n \in \Sigma^*, on a_1,a_2,\dots, a_n \in \Sigma.

1. \sigma(w)=a_1a_1a_2a_2\cdots a_na_n.
2. \sigma(w)=a_1a_2a_2a_3a_3a_3\cdots\overbrace{a_n\cdots a_n}^{n)}.
3. \sigma(w)=ww.
4. \sigma(w)=w.
5. \sigma(w)=\lambda.
6. \sigma(w)=a^{|w|}, on a\in \Sigma.
7. \sigma(w)=w^R.
8. \sigma(w)=\sigma_1(\sigma_2(w)), on \sigma_1,\sigma_2 són homomorfismes.